package recursion;

public class MiGong {
    public static void main(String[] args) {
        //用二维数组创建一个迷宫地图
        int[][] map = new int[8][7];
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        findWay(map,1,1);
        System.out.println("~~~~~~~出路的路线~~~~~~~");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
    /*
    * 1.参数map(二维数组)代表迷宫
    * 2.map中数字的含义:0代表这个点还没有走过,1代表障碍物墙,2代表这个点已经走过,3代表这个点4个方向都走不通
    * 3.走迷宫的策略定位上-右-下-左,也可以是其他的
    * 4.map[6][5]=2代表找到出路
    * 5.参数i,j代表起始位置map[i][j]
    * */
    public static boolean findWay(int[][] map,int i,int j) {
        if(map[6][5]==2) {
            return true;
        }else {
            //下面代码的目的,走没有走过的点,也就是数字为0的点,走过就标记为2,死点标记为3(4个方向都走不通的点为死点)
            //因为在没有走过的点中一定有一条通往出口的路,除非是死路
            if(map[i][j]==0) {//说明这个点没有走过,要开始走
                map[i][j]=2;//先把这个点标记为2,记录这个点现在我们已经走过了
                //按照策略开始走
                if(findWay(map,i+1,j)) {//向下走
                    return true;//return true代表向下可以走
                }else if(findWay(map,i,j+1)) {//向右走
                    return true;//return true代表向右可以走
                }else if(findWay(map,i-1,j)) {//向上走
                    return true;//return true代表向上可以走
                }else if(findWay(map,i,j-1)) {//向左走
                    return true;//return true代表向左可以走
                }else {
                    map[i][j]=3;//4个方向都走不通,把这个点标记为3
                    return false;//return false代表这个点4个方向都不可以走
                }
            }else {//map[i][j]不是0,就不需要走,返回false
                return false;
            }
        }
    }
}
